package com.LeetCode.Tree;

import org.junit.Test;

/**
 * 字典序的第k个数
 */
public class TrieTree {

    public int findKthNumber(int n, int k) {
        int prefix = 1;
        k--;
        while(k > 0){
            int cnt = getCnt(n,prefix);
            if(cnt <= k){//下一个前缀，往右跳 cnt 个数继续找
                k-= cnt;
                prefix++;
            }else{//往下找，这里只能跳一个数，把根节点跳过去
                k--;
                prefix *= 10;
            }
        }
        return prefix;
    }

    public int getCnt(long n , long prefix){
        int cnt = 0;
        for(long first = prefix, second = prefix + 1; first <= n; first *= 10, second *= 10){
            cnt += Math.min(n+1,second) - first;
        }
        return cnt;
    }

    @Test
    public void test(){
        int n = 13;
        int k = 2;
        System.out.println(findKthNumber(n,k));
        System.out.println(getCnt(200,10));
    }
}
